The present invention relates to public key encryption systems and more particularly to the generation of session parameters for use with public key protocols.
Public key data encryption systems are well-known and the more robust are based upon the intractability of the discrete log problem in a finite group. Such public key encryption systems utilize a group element and a generator of the group. The generator is an element from which each other group element can be obtained by repeated application of the underlying group operation, ie. repeated composition of the generator. Conventionally, this is considered to be an exponentiation of the generator to an integral power and may be manifested as a k fold multiplication of the generator or a k fold addition of the generator depending upon the underlying group operation. In such a public key encryption system, an integer k is used as a private key and is maintained secret. A corresponding public key is obtained by exponentiating the generator a with the integer k to provide a public key in the form xcex1k. The value of the integer k cannot be derived even though the value xcex1k is known.
The public and private keys may be utilized in a message exchange where one of the correspondents may encrypt the data with the recipient""s public key xcex1k. The recipient receives the encrypted message and utilizes his private key k to decrypt the message and retrieve the contents. Interception of the message will not yield the contents as the integer k cannot be derived.
A similar technique may be utilized to verify the authenticity of a message by utilizing a digital signature. In this technique, the transmitter of the message signs the message with a private key k and a recipient can verify that the message originated from the transmitter by decrypting the message with the transmitter""s public key xcex1k. A comparison between a function of the plain text message and of the recovered message confirms the authenticity of the message.
In both techniques, it is necessary to perform the exponentiation of the group element xcex1. To be secure, k must be a relatively large number and the exponentiation can therefore be relatively long. Where the exponent is used as a long-term public key, the time of computation is not of undue concern. However, in digital signature schemes, a short term session key is utilized together with the long-term public key. Each message is signed with a different private key k and the corresponding public session key xcex1k has to be computed and transmitted with the message. There is therefore the need for some efficiency in the exponentiation.
The computing time for the exponentiation can be reduced by utilizing an integer exponent k having a relatively low Hamming weightxe2x80x94that is, the number of 1""s in the binary representation of the integer is kept low or analogously in another radix, the exponent has few non-zero coefficients. However, integers having low Hamming weights are considered vulnerable to various attacks, including a square root attack, and so their use in encryption protocols is not encouraged.
It is therefore an object of the present invention to provide a method of computing the session parameters for public key exchange protocols that obviates or mitigates the above disadvantages.
In general terms, the present invention provides a method of computing an exponent for use in a public key exchange protocol in which an integer kxe2x80x2 is selected, having a Hamming weight less than a predetermined value. An exponentiation with the generator xcex1 is performed and the resultant intermediate session parameter xcex1kxe2x80x2 is mathematically combined with a secret value xcex3. xcex3 is derived from a random integer i which has a Hamming weight greater than the predetermined value. The mathematical combination of xcex3 with the intermediate session parameter produces a session parameter whose exponent has a Hamming weight greater than the predetermined value and as such is considered computationally secure.
Conveniently, the secret value xcex3 can be precomputed so that the real time exponentiation is confined to the generation of the exponent that utilizes the integer kxe2x80x2.
The method may be used with the multiplicative group Z*p or may be utilized with other groups such as elliptic curves over a finite field.